package first.forHuaWei.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC22
 * @description:
 * @author: 荣燊
 * @create: 2021-09-09 20:38
 **/
public class LC22 {
    // 括号生成，深度搜索DFS

    public static void main(String[] args) {

    }

    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if (n == 0) {
            return list;
        }
        bfs("", n, n, list);
        return list;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    public static void bfs(String curStr, int left, int right, List<String> res) {
        // 左右括号已经用尽，加入到res集合中
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        // 左括号的数量一定要大于右括号的数量才发生剪枝，剪枝就是避免重复
        if (left > right) {
            return;
        }
        if (left > 0) {
            bfs(curStr+"(", left-1, right, res);
        }
        if (right > 0) {
            bfs(curStr+")", left, right-1, res);
        }

    }
}
